package com.algorithm;

/**
 * 最大子序和(动态规划思想)
 */
public class MaximumSubarray {

    public static int maxSubArray(int[] nums) {
        int max = nums[0];
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            temp= Math.max(nums[i],nums[i]+temp);
            if (temp > max) {
                max = temp;
            }
        }
        return max;
    }

    public static void main(String[] args) {
//       int [] nums = {-2,1,-3,4,-1,2,1,-5,4};
//       int [] nums = {2,3};
        int[] nums = {-5, -4, -1, -7, -8};
        int i = maxSubArray(nums);
        System.out.println(i);
    }
}
